Traditionally, characters have been printed using metal type which allows very detailed rendering of a character, including subtle curves and very fine lines. In modern computer devices, characters are defined on raster devices such as video display terminals or by using a multi-pin print head. Characters can be printed on a surface or displayed on a video screen as a series of dots which are printed or turned on in order to approximate as closely as possible the ideal shape of the character. When characters are small enough relative to the resolution of the display device, choosing which pixels should be displayed to accurately represent the character becomes more complex than when the character is large. A typical video monitor can display about 72 pixels per inch. At this resolution it is difficult to display legibly most type faces smaller than about twenty pixels tall.
An ideal representation of the character is usually defined in "character space" at very high resolution as one or more areas bounded by an outline or path. A character consists of one or more continuous black areas. For instance the letter "O" consists of a single closed loop, the letter "d" consists of a loop connected to a line and the letter "i" consists essentially of a dot a short distance away from a line which may have additional details such as serifs. One way of describing a character involves defining an outline of the outer edge of each contiguous black portion of the character and then filling that outline to display the character. Since characters are usually printed in dark ink on a light background, one can describe filled areas as black but one skilled in the art will recognize that characters which are light on a dark background, commonly used in video displays, are also within the teachings of this invention. This path can be represented as a sequential series of curves and/or linear line segments called edges. If a black area has interior white spaces as, for instance, in the letter "O38 , each interior white area can also be defined by a path consisting of a series of edges.
When tracing or displaying such a character, it is generally useful to trace the edges in a consistent direction, either clockwise or counter-clockwise. If edges of an outside path are traced in the counter-clockwise direction, then the area to the left of that edge will always be black and the area to the right will always be white. If the path is traced in the clockwise direction, the black area will be on the right of the edge. Enclosed white areas should be traced in the direction opposite to the exterior path so that the black area is on the same relative side of the edge.
When a character is displayed on a raster device, those pixels which fall within the black area of the character should be displayed, that is, they should be printed on a surface or turned on for a video display. At high resolution or when the character is very large, multiple pixels may fall within each black area and the character can be displayed in great detail. When the character is reduced to a small size, however, or the resolution of the device is limited, certain black areas may no longer cover multiple pixels and in fact may cover only a fraction of a pixel. Displaying small characters on a device of limited resolution has been a persistent problem in the past. This is illustrated in the figures by a character on an 8.times.10 matrix. In FIG. 1 the outline of the character "S" is illustrated as filled at very high resolution. The raster display, however can only turn on or off entire pixels.
One prior approach to this problem is the center point fill method, illustrated in FIG. 2. A pixel is displayed only if the center of that pixel falls within or on the boundaries of a black area, illustrated by pixels 40-44. Where only a limited number of pixels are available to display the character, there are gaps or dropouts 50-52 in the black areas so that it may be difficult to recognize the character. An alternative way of displaying the character, called area fill, is to turn on all pixels which intersect or fall within the outline of the character. The result, shown in FIG. 3, is that too many pixels are turned on, leading to blobs which also make the character difficult to recognize. At higher resolution both of these methods work successfully but at low resolution characters become difficult to recognize.